/* AlgorithmComparison.java
 *
 * Cermelo Woodgett
 *
 * Created on January 25, 2007, 11:05 PM
 *
 * This program supplies the integer array to the sort algorithms and
 * then prints the times.
 *
 */

import java.util.Random;

public class AlgorithmComparison {
    
    static private char[][] RadArray;
    
    public static void main(String args[]) {
        
        long sTime = 0; // timer start time
        long fTime = 0;  //timer end time
        long ssTime = 0; // SelectionSort sort time
        long bsTime = 0; // BubbleSort sort time
        long isTime = 0; // InsertSort sort time
        long msTime = 0; // MergeSort sort time
        long qsTime = 0; // QuickSort sort time
        long rsTime = 0; // RadixSort sort time
        long tsTime = 0; // TreeSort sort time
        
        //Sum variables for the average
        int count = 0; // counts the number of instances
        long totalAvg = 0;
        
        // Total times for all sorts
        float totalSSTime = 0;
        float totalBSTime = 0;
        float totalISTime = 0;
        float totalQSTime = 0;
        float totalMSTime = 0;
        float totalRSTime = 0;
        float totalTSTime = 0;
        
        System.out.println("Items"+'\t'+"Sel"+'\t'+"Bub"+'\t'+"Ins"+'\t'+"Quick"+'\t'+"Merge"+'\t'+"Rad"+'\t'+"Tree");
        System.out.println("-------------------------------------------------------------------------");
        for (int arraySize = 500; arraySize <= 10000; arraySize += 500) {
            
            int[] theArray = new int[arraySize];
            for(int x = 0; x < arraySize; x++) {
                theArray[x] = (int) (Math.random() * 1000000000);
            }
            int[] yourArray = new int[arraySize];
            
            // Initialize yourArray to theArray
            for( int k = 0; k < arraySize; k++) {
                yourArray[k] = theArray[k];
            }
            
            // Run SelectionSort and get elapsed time
            sTime = System.currentTimeMillis();
            SelectionSort.SelSort(yourArray, arraySize);
            fTime = System.currentTimeMillis();
            ssTime = fTime - sTime;
            
            // Reinitialize yourArray to theArray
            for( int k = 0; k < arraySize; k++) {
                yourArray[k] = theArray[k];
            }
            
            // Run BubbleSort and get elapsed time
            sTime = System.currentTimeMillis();
            BubbleSort.bubbleSort(yourArray, arraySize);
            fTime = System.currentTimeMillis();
            bsTime = fTime - sTime;
            
            // Reinitialize yourArray to theArray
            for( int k = 0; k < arraySize; k++) {
                yourArray[k] = theArray[k];
            }
            
            // Run BubbleSort and get elapsed time
            sTime = System.currentTimeMillis();
            InsertionSort.insertionSort(yourArray, arraySize);
            fTime = System.currentTimeMillis();
            isTime = fTime - sTime;
            
            // Reinitialize yourArray to theArray
            for( int k = 0; k < arraySize; k++) {
                yourArray[k] = theArray[k];
            }
            
            // Run QuickSort and get elapsed time
            sTime = System.currentTimeMillis();
            QuickSort.QuickSort(yourArray, 0, arraySize - 1);
            fTime = System.currentTimeMillis();
            qsTime = fTime - sTime;
            
            // Reinitialize yourArray to theArray
            for( int k = 0; k < arraySize; k++) {
                yourArray[k] = theArray[k];
            }
            
            // Run MergeSort and get elapsed time
            sTime = System.currentTimeMillis();
            MergeSort.MergeSort(yourArray, 0, arraySize - 1);
            fTime = System.currentTimeMillis();
            msTime = fTime - sTime;
            
            // Reinitialize yourArray to theArray
            for( int k = 0; k < arraySize; k++) {
                yourArray[k] = theArray[k];
            }
            
            MakeRadArray(yourArray);
            
            // Run RadixSort and get elapsed time
            sTime = System.currentTimeMillis();
            RadixSort.RadixSort(RadArray);
            fTime = System.currentTimeMillis();
            rsTime = fTime - sTime;
            
             // Reinitialize yourArray to theArray
            for( int k = 0; k < arraySize; k++) {
                yourArray[k] = theArray[k];
            }
            
            // Run TreeSort and get elapsed time
            sTime = System.currentTimeMillis();
            TreeSort.TreeSort(yourArray, arraySize);
            fTime = System.currentTimeMillis();
            tsTime = fTime - sTime;
            
            // Add times to total times
            totalSSTime += ssTime;
            totalBSTime += bsTime;
            totalISTime += isTime;
            totalQSTime += qsTime;
            totalMSTime += msTime;
            totalRSTime += rsTime;
            totalTSTime += tsTime;
            
            count ++;
            
            // Print all the times
            System.out.print(arraySize + "\t");
            System.out.print(ssTime + "\t");
            System.out.print(bsTime + "\t");
            System.out.print(isTime + "\t");
            System.out.print(qsTime + "\t");
            System.out.print(msTime + "\t");
            System.out.print(rsTime + "\t");
            System.out.print(tsTime + "\t");
            System.out.print("\n");
        }
        System.out.println(" ");
        System.out.println(" ");
        
        // Print the average for each sort
        System.out.println("AVG:    "+totalSSTime/count+'\t'+totalBSTime/count+'\t'+ totalISTime/count+'\t'+totalQSTime/count+'\t'+totalMSTime/count+'\t'+totalRSTime/count+'\t'+totalTSTime/count);
    }
    
//    The following converts the integer array into a char array
//    for RadixSort.
    private static void MakeRadArray(int[] myArray) {
        int maxSize = myArray.length;
        
        RadArray = new char[maxSize][];
        for (int i = 0; i < maxSize; i++) {
            RadArray[i] = new char[10];
        }
        
        for (int i = 0; i < maxSize; i++) {
            for (int j = 0; j < 9; j++) {
                int power = (int)java.lang.Math.pow((double)10, (double)8-j);
                RadArray[i][j] = (char)((myArray[i]/power) % 10);
            }
        }
        
    }
    
}
